"""
小明家住在二楼，每次回家都需要经过一个有 10 层台阶的楼梯。
小明每次可以选择一步走一级台阶或者一步走两级台阶。
请帮小明计算他从楼下到家一共有多少种走法。


打个比方，小明可以选择每次都走一级台阶，那么他回家一共需要走十步，这是其中的一种走法。
不然，他还可以选择一次走两级台阶，那么他回家一共需要走五步，这是另外一种走法。
除此之外，还有很多种不同的走法，现在我们要做的是把所有可能的走法数量统计出来。
"""
"""在正式写程序之前，我们先一起整理一下该问题的解题思路。

首先考虑小明走最后一步的情况，
他要么是从第九级台阶再走一级到第十级，要么是从第八级台阶走两级到第十级。
也就是说，要想到达第十级台阶，最后一步一定是从第八级或者第九级台阶开始的。
也就是说，如果已知从地面到第八级台阶一共有 X 种走法，从地面到第九级台阶一共有 Y 种走法，那么从地面走到第十级台阶一定是 X 和 Y 之和。
即 F(10) = F(9) + F(8)
推而广之，对于 F(n)，我们可以通过 F(n-1) 和 F(n-2) 计算得到，即 F(n) = F(n-1) + F(n-2)。

"""


def upstairs(n):
    """ 非递归 """
    if n < 1:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    a = 1
    b = 2

    for i in range(3, n + 1):
        a, b = b, a + b
    return b


def upstairs_v2(n):
    """ 递归 """
    if n == 0 or n == 1:
        return 1
    return upstairs_v2(n - 1) + upstairs_v2(n - 2)


if __name__ == '__main__':
    print(upstairs(10))
    print(upstairs_v2(10))
